package com.game.astar;

/**
 * 基于A* 寻路优化
 * 添加入深度搜索驱动
 * @author 庄宏晓
 * @date 2013-6-20
 */
public class DAStarDrive 
{
	/*a:记录数字的数组*/
	int[] a = new int[25];
	int[] cnt = new int[25];
	char[] out = new char[1000];
	int deep;
	
	/*最后的局面中心的结果数字*/
	int res;
	
	/*判断是否到达目标状态*/
	private boolean ok(int[] a)
	{
		int tmp = this.a[7];
		
		if( tmp!=this.a[8] || tmp != this.a[9] || tmp != this.a[12] || tmp != this.a[13] || tmp != this.a[16] || tmp != this.a[17] || tmp != this.a[18] )  
		{	        
			return false; 
		}
		
		return true;  
	}
	
	//旋转   
	private void change(int[] cur,int a,int b,int c,int d,int e,int f,int g)  
	{  
	    int tmp=cur[a];  
	    cur[a] = cur[b];
	    cur[b] = cur[c];
	    cur[c]=cur[d];
	    cur[d]=cur[e];
	    cur[e]=cur[f];
	    cur[f]=cur[g];
	    cur[g]=tmp;  
	}  
	  
	//计算8个标准位置中数量最多的数字有多少个   
	private int count(int[] a)  
	{  
	    /*重置数组为0*/
	    for (int i = 0; i < cnt.length; i++) {
			cnt[i] = 0;
		}
	    cnt[a[7]]++;cnt[a[8]]++;cnt[a[9]]++;  
	    cnt[a[12]]++;cnt[a[13]]++;cnt[a[16]]++;  
	    cnt[a[17]]++;cnt[a[18]]++;  
	    cnt[2]=cnt[1]>cnt[2]?cnt[1]:cnt[2];  
	    
	    if(cnt[2] >= cnt[3])
	    {
	    	return cnt[2];
	    }
	    
	    return cnt[3];  
	}  
	  
	//pre：上一次递归移动的方向   
	//now:当前递归的步数   
	public boolean dfs(int[] a, int now, int pre) {  
	    //剪枝：如果当前可以递归的深度已经小于局面中心数字所需量   
	    if (deep - now  < 8 - count(a))  
	       return false;  
	    //超过当前的搜索深度   
	    if (now >= deep)   
	        return false;  
	    int[] temp = new int[25];           //备份当前的局面   
	    for (int i = 0; i < 8; ++i) 
	    {  
	        //如果前后两次拉动的方向恰好相反，那么就剪枝   
	        if( (pre==0 && i==5) || (pre==5 && i==0) ) continue;  
	        if( (pre==1 && i==4) || (pre==4 && i==1) ) continue;  
	        if( (pre==2 && i==7) || (pre==7 && i==2) ) continue;  
	        if( (pre==3 && i==6) || (pre==6 && i==3) ) continue;  
	        for (int j = 1; j <= 24; ++j) {  
	            temp[j] = a[j];  
	        }  
	        switch(i) {  
	        case 0:out[now]='A';change(temp,1,3,7,12,16,21,23);break;  
	        case 1:out[now]='B';change(temp,2,4,9,13,18,22,24);break;  
	        case 2:out[now]='C';change(temp,11,10,9,8,7,6,5);break;  
	        case 3:out[now]='D';change(temp,20,19,18,17,16,15,14);break;  
	        case 4:out[now]='E';change(temp,24,22,18,13,9,4,2);break;  
	        case 5:out[now]='F';change(temp,23,21,16,12,7,3,1);break;  
	        case 6:out[now]='G';change(temp,14,15,16,17,18,19,20);break;  
	        case 7:out[now]='H';change(temp,5,6,7,8,9,10,11);break;  
	        }  
	        if (ok(temp)) {  
	            res = temp[7];  
	            out[now+1] = '0';  
	            return true;  
	        }  
	        if (dfs(temp, now + 1, i))  
	            return true;  
	  
	    }  
	    return false;  
	}  
}
